package zuoshen_video;

import org.junit.Test;

public class StringProblem {
    //KMP算法实现及升级
    class KMP {
        public int[] getNext(String s) {
            int len = s.length();
            int[] next = new int[len];

            //初始化固定值
            next[0] = -1;
            next[1] = 0;

            //last是当前i之前的最大前后缀长度，i为遍历到的位置
            int last = 0, i = 2;
            while (i < len) {
                if (s.charAt(i - 1) == s.charAt(last)) {
                    //长度对应到下标，刚好是当前最大长度的前后缀后面那个位置
                    //若前缀之后那个位置与i-1位置匹配，则i前的最大前后缀为此时的最大前后缀加一
                    next[i++] = ++last;
                } else if (last > 0) { //若此位置之前还有共同前后缀，继续探查
                    last = next[last];
                } else {
                    next[i++] = 0; //已经没有共同前后缀了，设为0
                }
            }
            return next;
        }

        public int kmp(String p, String q) {
            int[] next = getNext(p);
            int s1 = 0, s2 = 0, len1 = p.length(), len2 = q.length();
            while (s1 < len1 && s2 < len2) {
                if (p.charAt(s1) == q.charAt(s2)) {
                    //两者当前字符匹配，共同进一位
                    s1++;
                    s2++;
                } else {
                    //不匹配，通过next跳过某些位置
                    if (next[s2] == -1) {
                        //在q的首字符位置就已经不匹配, s1进一格,表示无捷径可走
                        s1++;
                    } else {
                        //尽管逻辑上移动的是p，实际不动s1，让s2的匹配位置移动、此时q前面s2个字符刚好与p的后缀重合，s2位置对应之前产生不匹配的那个位置
                        s2 = next[s2];
                    }
                }
            }
            //s2越过了q的范围，此时在p和q必然都停在q最后一个字符的后一个位置，因此将s1-q的长度就能得到匹配位置的首位置；否则返回没找到
            return s2 == q.length() ? s1 - s2 : -1;
        }
    }

    //马拉车算法，计算最大回文子串
    class Manacher {
        //马拉车算法的简单实现方法，要求每个字符串中间加入分割符，使得扩散比对能够对于奇偶长度透明
        public String addExtraSeperators(String s) {
            StringBuilder sb = new StringBuilder("#");
            for (int i = 0; i < s.length(); i++) {
                sb.append(s.charAt(i));
                sb.append("#");
            }
            return sb.toString();
        }

        public String solveExtraSegerators(String s) {
            StringBuilder sb = new StringBuilder();
            for (int i = 1; i < s.length(); i += 2) {
                sb.append(s.charAt(i));
            }
            return sb.toString();
        }
        
        public String maxPalinStr(String s) {
            int len;
            if (s == null || (len = s.length()) == 0) return "";
            s = addExtraSeperators(s);
            int max = 0;
            len = s.length();
            String res = null;
            int C = -1; //C:最大回文右边界对应的回文中心
            int R = -1; //R:最大回文右边界
            int[] palin = new int[len]; //回文半径数组，其值至少为1，表示回文半径是自身
            for (int i = 0; i < len; i++) {
                /* 
                    1. R > i, 表示i在回文右边界内
                    R == i时，最好的情况是palin[i'] == 1, 此时为了验证i左右两边是否相等也是要进行扩散比对的，因此不能进行缩减

                    2. 2 * C - i 代表i关于对称中心C的镜像位置i'
                    这可能是Manacher最复杂的地方
                    xxxxxxabc_d_cba ,i为b的位置， 2 * C就是 xxxxxxabc_d_cbaxxxxxx【以d未镜像复制一遍，因为数组下标少一位，因此d自身不复制】
                    而2 * C - i => axxxxxx === xxxxxxa => 因此此时的位置就是刚好是左边的b

                    3. R - i
                    i距离回文右边界的距离

                    min的计算对于i在右边界类的三种情况都是统一的，重点在于对后面的处理
                    这句话含义就是求得 ** 当前的i可以不用进行扩散比对的距离 ** ，而**不一定**是真正的palin[i]
                    对于情况1,2,3的确是palin[i],但是对于4还需要进行扩散，升级palin[i]
                    但是无论怎样，从i开始的palin[i]个部分可以不用进行扩散比对
                */
                palin[i] = R > i ? Math.min(palin[2 * C - i], R - i) : 1;
                
                /* 
                    上一步得到的越过的距离，这里开始进行扩散比对
                    对于情形2,3,比对一次直接跳出循环
                */
                int hi = i + palin[i], lo;
                while ((lo = i - palin[i]) > -1 && (hi = i + palin[i]) < len) { //
                    if (s.charAt(hi) == s.charAt(lo)) palin[i]++; //palin[i]的修改本身会作用到lo和hi的修改
                    else break;
                }

                if (i + palin[i] > R) {
                    R = i + palin[i];
                    C = i;
                }

                if (palin[i] > max) {
                    max = palin[i];
                    res = s.substring(lo + 1, hi);
                }   
            }
            //因为最大长度实际上是加了#号的最大长度一半，且加了#后最大回文子串必定为奇数个数串，
            //因此除以2导致刚刚好去除掉了多余的#数量，即max实际就是最大回文串长度
            //最后，加了#也会使得最外层必定为#

            res = solveExtraSegerators(res);
            System.out.println(max);        
            return res;
        }        
    }

    @Test
    public void test() {
        KMP k = new KMP();
        // System.out.println(k.kmp("ababababbp", "bbp"));
        // System.out.println((Long.MAX_VALUE + "").length());

        Manacher m = new Manacher();
        System.out.println(m.maxPalinStr("abcdcbatttabcdcf"));
    }
}
